// 动态公式
// d1==0
// n1=n1+l1 l1>l2 或者 l1==l2 d1<d2
// n2=n2+d1+l1 l1>l2
//
// n1=n1+d2+l2 l1<l2 或者 l1==l2 d1>d2
// n2=n2+l2 l1<l2


//扫描法，复杂度为 n+m
//生产增量包
function makeChunk(s1,s2) {
  var n=s1.length,m=s2.length;//长度
  var n1=0,n2=0;//扫描点
  const chunkArr=[]
//开始扫描
  while (n1<n&&n2<m){
    //相等
    if(s1[n1]===s2[n2]){
      let nn1=n1+1;
      let nn2=n2+1;
      while (nn1<n&&nn2<m&&s1[nn1]===s2[nn2]){
        nn1++;
        nn2++;
      }
      chunkArr.push(['e',n1,nn1-n1])
      n1=nn1;
      n2=nn2;
    }else{
      let d1=0;
      let d2=0;
      if(n1+1<n){
        d2=1;
      }
      if(n2+1<m){
        d1=1;
      }
      if(d1===1&&d2===1){
        if(s1[n1+1]!==s2[n2+1]){
          while (n2+d1<m&&s1[n1]!==s2[n2+d1]){
            d1++;
          }
          while (n1+d2<n&&s1[n1+d2]!==s2[n2]){
            d2++;
          }
        }
      }

      if(d1===d2){
        //替换
        chunkArr.push(['r',s2.substr(n2,1)])
        n1=n1+1;
        n2=n2+1;
      }else if(d1<d2){
        //增加
        chunkArr.push(['a',s2.substr(n2,1)])
        n2=n2+1;
      }else{
        //删除
        chunkArr.push(['d',n1,1,s1.substr(n1,1)])
        n1=n1+1;
      }
    }
    //超出的处理
    if(n1>=n&&n2<m){
      var i=s1.indexOf(s2[n2])
      if(i===-1){
        chunkArr.push(['a',s2.substr(n2,1)])
        n1=0;
        n2=n2+1;
      }else{
        n1=i;
      }
    }
  }
  //压缩指令
  var minChunk=[]
  for(let i=0;i<chunkArr.length;i++){
    const arr=chunkArr[i];
    if(arr[0]==='r'){
      chunkArr[i]=[arr[0],arr[1]]
    }
    var lastArr=minChunk[minChunk.length-1];
    if(arr[0]==='a'&&lastArr&&lastArr[0]==='a'){
      lastArr[1]=lastArr[1]+arr[1];
    }else{
      minChunk.push(arr)
    }
  }
  return minChunk;
}

//执行增量包
function execChunk(s1,chunk){
  var ns=''
  for(let i=0;i<chunk.length;i++){
    const arr=chunk[i];
    if(arr[0]==='e'){
      ns=ns+s1.substr(arr[1],arr[2])
    }else if(arr[0]==='r'){
      ns=ns+arr[1]
    }else if(arr[0]==='a'){
      ns=ns+arr[1]
    }
  }
  return ns
}


//定义两个字符
var s1="abcdabcdabcdabcd",
  s2="abcdabcdabcdabcdabcdabcdabcdabcder";
const chunk=makeChunk(s1,s2);
console.log(chunk)
const nstr=execChunk(s1,chunk)
console.log(nstr===s2)
console.log(nstr)
